public class StarAdvanture {

	public static void main(String[] args) {
		String[] level ={"0123456789",
				 "1123456789",
				 "2223456789",
				 "3333456789",
				 "4444456789",
				 "5555556789",
				 "6666666789",
				 "7777777789",
				 "8888888889",
				 "9999999999"};
		
		System.out.println(mostStars(level));
		
	}

	public static int mostStars(String[] level) {
	
		int totalStart = 0;
		for(int i=0;i<3;i++){
			totalStart+=singleMove(level);
			for(int j=0;j<level.length;j++){
				System.out.println(level[j]);
			}
			System.out.println(totalStart);
		}
		
		return totalStart;
	}

	public static int singleMove(String[] level){
		int[][] collection = new int[level.length][level[0].length()];
		String[][] path = new String[level.length][level[0].length()];
		for(int i=0;i<level.length;i++){
			for(int j=0;j<level[0].length();j++){
				int star = Integer.parseInt(level[i].substring(j,j+1));
				int masStar=0;
				boolean chooseUp=false;
				//collection[i][j] = max{colleciton[i][j-1], collection[i-1][j]}
				if(i>0){
					int compare = collection[i-1][j];
					if(masStar<compare){
						masStar = compare;
						chooseUp=true;
					}
				}
				if(j>0){
					int compare = collection[i][j-1];
					if(masStar<compare){
						masStar = compare;
						chooseUp=false;
					}
				}
				//record move path
				if(chooseUp&&i>0){
					path[i][j]=path[i-1][j]+i+""+j;
					
				}
				else if(!chooseUp&&j>0){
					path[i][j]=path[i][j-1]+i+""+j;
				}
				else
					path[i][j]=i+""+j;
				
				//System.out.println(path[i][j]);
				collection[i][j]=star+masStar;
				//System.out.println(collection[i][j]);
			}
		}
		//revise the original apple bucket according to the path
		String finalPath = path[level.length-1][level[0].length()-1];
		for(int i=0;i<finalPath.length();i+=2){
			int x = Integer.parseInt(finalPath.substring(i, i+1));
			int y = Integer.parseInt(finalPath.substring(i+1,i+2));
			char[] c=level[x].toCharArray();
			c[y]='0';
			level[x] = String.valueOf(c);

		}
		
		return collection[level.length-1][level[0].length()-1];
	}
}
